import java.util.Arrays;

class Solution {
    public int[] diStringMatch(String s) {

        int n=s.length();
        int[] ret=new int[n+1];
        int left=0;
        int right=n;
        for(int i=0;i<n;i++){
            switch(s.charAt(i)){
                case 'I':
                    ret[i]=left++;
                    break;
                case 'D':
                    ret[i]=right--;
                    break;
            }
        }
        ret[n]=right;
        return ret;

    }
}


class Solution1 {
    public int findContentChildren(int[] g, int[] s) {
        int ret=0;
        int n=g.length;
        int nn=s.length;

        Arrays.sort(s);
        Arrays.sort(g);
        int left=0;

        for(int i=0;i<n;){
            if(left==nn) return ret;
            if(g[i]<=s[left]){
                i++;
                left++;
                ret++;
            }else{
                left++;
            }
        }
        return ret;



    }
}


class Solution2 {
    public String optimalDivision(int[] nums) {
        int n=nums.length;
        if(n==1) return nums[0]+"";
        if(n==2) return nums[0]+"/"+nums[1];
        StringBuilder s=new StringBuilder();
        s.append(nums[0]);
        s.append('/');
        s.append('(');
        s.append(nums[1]);



        for(int i=2;i<n;i++){
            s.append('/');
            s.append(nums[i]);
        }
        s.append(')');
        return s.toString();

    }
}


class Solution3 {
    public int jump(int[] nums) {
        if(nums.length==1) return 0;
        int ret=0;
        int count=0;
        Queue<int[]> q=new LinkedList<>();
        q.add(new int[]{0,nums[0]});

        while(!q.isEmpty()){
            int sz=q.size();
            int cur=0;
            int max=0;
            ret++;


            for(int i=0;i<sz;i++){
                int[] arr=q.poll();
                cur=arr[0];
                max=Math.max(cur+arr[1],max);
                if(max>=nums.length-1) return ret;
            }

            for(int i=cur+1;i<=max;i++){
                q.add(new int[]{i,nums[i]});
            }
        }
        return ret;


    }
}